#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
/**
 * @brief
 * 1 <= arr.length <= 500
 * 0 <= arr[i] <= 10^4
 *  max 2^13
 */
class Solution
{
public:
    vector<int> sortByBits(vector<int> arr)
    {
        vector<int> ans;
        vector<pair<int, int>> tmpAns;
        for (int a : arr)
        {

            // count 1 bits
            int num = a, bitsCount = 0;
            while (num)
            {
                num &= num - 1;
                bitsCount++;
            }
            tmpAns.push_back({bitsCount, a});
        }
        sort(tmpAns.begin(), tmpAns.end());
        for (auto iter : tmpAns)
        {

            ans.push_back(iter.second);
        }
        return ans;
    }

    vector<int> sortByBits_1(vector<int> arr)
    {
        sort(arr.begin(), arr.end(), [](const int &a, const int &b)
             {
            int countA = __builtin_popcount(a), countB = __builtin_popcount(b);
            return countA==countB ? a<b:countA<countB; });
        return arr;
    }

    int bitsCount(int number)
    {
        int c = 0;
        while (number)
        {
            c++;
            number = number & (number - 1);
        }
        return c;
    }
    vector<int> sortByBits_3(vector<int> arr)
    {
        map<int, vector<int>> mp;

        for (auto a : arr)
        {
            mp[bitsCount(a)].push_back(a);
        }

        vector<int> ans;
        for (auto m : mp)
        {

            sort(m.second.begin(), m.second.end());
            ans.insert(ans.end(), m.second.begin(), m.second.end());
        }
        return ans;
    }
};
int main()
{
    Solution s;
    vector<int> res = s.sortByBits_3({0, 1, 2, 3, 4, 5, 6, 7, 8});
    for (int r : res)
    {
        cout << r << " ";
    }
    cout << endl;
    return 0;
}
